#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：

输入：nums = [1], target = 0
输出：-1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//能感觉到是二分法 峰值
int search(vector<int>& nums, int target) {

    int left = 0, right = nums.size()-1;

    while(left <= right){
        int mid = (left + right) / 2;
        if(nums[mid] == target)
            return mid;

        //4,5,6,7,0,1,2
        //如果 右边有序
        else if(nums[mid] < nums[right]){
            if(nums[mid] < target && target <= nums[right])
                left = mid+1;//在有序区间搜索
            else
                right = mid-1;//
        }
        else{
            if(nums[left] <= target && target < nums[mid])
                right = mid-1;
            else
                left = mid+1;
        }

    }
    return -1;



}

//todo
int search(vector<int>& nums, int target) {
    // if(nums.size()==1&&target==nums[0])
    //   return 0;


    int low = 0, high = nums.size()-1;
    //4 5 6 7 1 2 3  比如找的是1
    // mid=6  low=4 high=3  val=1;

    while (low<=high){

        int mid =low+(high-low)/2;

        //边界需要判断一下 否则似乎low 和high 被省略了......
        if (nums[mid]==target)
            return mid;
        if (nums[low]==target)
            return low;
        if (nums[high]==target)
            return high;

        //如果左边有序
        if (nums[mid]>nums[low])
        {   //这时候相当于有序数组了
            if (target>nums[low]&&target<nums[mid])
                high=mid-1;
            else{
                //说明没有在low -mid 区间
                low=mid+1;
            }


        } else{
            //在右边有序的寻找 5 4 3 2 1
            if (target<nums[low]&&target>nums[mid]){
                low=mid+1;
            } else{
                //说明了什么 没有在 mid 到high区间 寻找low 到 mid-1区间
                high=mid-1;

            }
        }

    }
    return -1;
}


